//统计所有小于非负整数 n 的质数的数量。 
//
// 
//
// 示例 1： 
//
// 输入：n = 10
//输出：4
//解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
// 
//
// 示例 2： 
//
// 输入：n = 0
//输出：0
// 
//
// 示例 3： 
//
// 输入：n = 1
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 0 <= n <= 5 * 106 
// 
// Related Topics 数组 数学 枚举 数论 
// 👍 793 👎 0

package com.cute.leetcode.editor.cn;
public class CountPrimes {
    public static void main(String[] args) {
        Solution solution = new CountPrimes().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 直接双重暴力搜的话会超时
     */
    class Solution {
        public int countPrimes1(int n) {
            if (n<3) return 0;
            if (n==3) return 1;
            int res = 2;
            for (int i = 5; i < n ; i+=2) {//排除偶数的优化
                boolean flag = true;
                for (int j = 2; j*j <= i ; j++) {//小于根号n的优化
                    if (i%j==0){
                        flag = false;
                        break;
                    }
                }
                if (flag) res++;
            }
            return res;
        }

        /**
         * 厄拉多塞筛选法：
         * 将当前素数的所有倍数都排除掉，会省去很多时间
         */
        public int countPrimes(int n) {
            boolean[] notPrime = new boolean[n+1];
            int res = 0;
            for (int i = 2; i < n ; i++) {
                if (!notPrime[i]){
                    res++;
                    for (int j = 2; j*i <= n ; j++) {//排除素数所有的倍数
                        notPrime[j*i]=true;
                    }
                }
            }
            return res;
        }

}
//leetcode submit region end(Prohibit modification and deletion)

}